package LimitedTimeGame.Day_0131;

/**
 * @author zxc
 * @date 2023/01/31 12:23
 **/

/**
 * 题目 ：最长等差数列
 * 题目详述 ：
 * 给你一个整数数组nums，返回 nums中最长等差子序列的长度。
 * 回想一下，nums 的子序列是一个列表nums[i1], nums[i2], ..., nums[ik] ，
 * 且0 <= i1 < i2 < ... < ik <= nums.length - 1。
 * 并且如果seq[i+1] - seq[i](0 <= i < seq.length - 1) 的值都相同，那么序列seq是等差的。
 *
 * 提示：
 * 2 <= nums.length <= 1000
 * 0 <= nums[i] <= 500
 */
public class LongestArithSeqLength {
    /**
     * 思路 ：
     * 由于要求取最长等差子序列长度，即使用动态规划来求解;
     *
     * 假设f(i , j)为长度为i数组nums中差值为j的最长等差子序列长度;
     * 状态转移方程 ：
     * 1.一般情况
     * f(i , d) = f(j , d) + 1;
     * 条件 ：|nums[i] - nums[j]| == d；
     * 2.特殊情况 ：
     * 若是nums数组中有且仅有一个元素时，f(1,j) == 0;
     * ===》 但同时若是nums数组中添加一个元素的话，即可以构成长度为2的等差子序列;
     * @param nums
     * @return
     */
    public int longestArithSeqLength(int[] nums) {
        // 获取nums数组长度
        int len = nums.length;
        // 假设f(i,j)为长度为i数组中差值为j的最长等差子序列;
        int[][] temp = new int[len][1001];
        // 定义变量maxLength，来记录nums数组中最长等差子序列的长度;
        int maxLength = 0;
        // 遍历nums[i] && nums[j] ,同时需要满足 i < j 条件;
        for(int i = 1 ; i < len ; i++){
            for(int j = 0 ; j < i ; j++){
                // 由于nums数组并不是顺序排列的，即很有可能出现nums[i] - nums[j] == 负数的情况；
                // ===》 即，为方便temp数组进行存储，选择将d + 500变为正整数;
                int d = nums[i] - nums[j] + 500;
                // 状态转移方程 ：f(i , d) = f(j , d) + 1;
                temp[i][d] = temp[j][d] + 1;
                maxLength = Math.max(maxLength , temp[i][d]);
            }
        }
        // 当nums数组中有且仅有一个元素时，则f(0,j) == 0;
        // 同时，若是nums数组有两个元素时，则值为2;
        return maxLength + 1;
    }
}
